# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 插入排序
# 基本思想: 从数组第二个元素开始遍历，当前元素左侧维持排序，将当前元素插入到左侧合适位置，插入位置到当前下标区间元素右移,直到遍历所有元素
# 时间复杂度: 最好O(n),最坏O(n^2),平均(n^2)
# 空间复杂度: 最好0(已经排好序),最坏O(n)(逆序),平均O(1)
# 稳定性: 稳定
from sort.arr_util import random_scale_arr


def insert_sort(num_arr):
    for i in range(1, len(num_arr)):
        tmp = num_arr[i]
        j = i
        while j > 0 and num_arr[j - 1] > tmp:
            num_arr[j] = num_arr[j - 1]
            j -= 1
        num_arr[j] = tmp


if __name__ == '__main__':
    arr = [1, 2, 5, 7, 6, 5, 4]
    insert_sort(arr)
    print(arr)
    arr2 = random_scale_arr(20, 500)
    insert_sort(arr2)
    print(arr2)
